package com.example.tree;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BinarySearchTree {

    private TreeNode root;

    // 查找节点
    public boolean contains(int value) {
        return search(root, value) != null;
    }

    // 插入节点
    public void insert(int value) {
        root = insert(root, value);
    }

    private TreeNode insert(TreeNode node, int value) {
        if (node == null) {
            return new TreeNode(value);
        }

        if (value < node.val) {
            node.left = insert(node.left, value);
        } else if (value > node.val) {
            node.right = insert(node.right, value);
        } else {
            // 如果值相等，则不插入（BST不允许重复值）
            return node;
        }

        return node;
    }

    // 删除节点
    public void delete(int value) {
        root = delete(root, value);
    }

    private TreeNode delete(TreeNode node, int value) {
        if (node == null) return null;

        if (value < node.val) {
            node.left = delete(node.left, value);
        } else if (value > node.val) {
            node.right = delete(node.right, value);
        } else {
            // 找到要删除的节点
            if (node.left == null && node.right == null) {
                // 情况1：没有子节点
                return null;
            } else if (node.left == null) {
                // 情况2：只有右子节点
                return node.right;
            } else if (node.right == null) {
                // 情况3：只有左子节点
                return node.left;
            } else {
                // 情况4：有两个子节点
                // 找到右子树的最小节点
                TreeNode successor = findMin(node.right);
                node.val = successor.val;
                node.right = delete(node.right, successor.val);
            }
        }

        return node;
    }

    // 查找最小值节点
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 查找最大值节点
    private TreeNode findMax(TreeNode node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // 查找节点并返回
    private TreeNode search(TreeNode node, int value) {
        while (node != null) {
            if (value < node.val) {
                node = node.left;
            } else if (value > node.val) {
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }

    // 前序遍历
    public void preOrderTraversal() {
        preOrderTraversal(root);
        System.out.println();
    }

    private void preOrderTraversal(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }

    // 查找树的最小值
    public int findMinValue() {
        if (root == null) throw new IllegalStateException();
        return findMin(root).val;
    }

    // 查找树的最大值
    public int findMaxValue() {
        if (root == null) throw new IllegalStateException();
        return findMax(root).val;
    }

    // 检查是否是有效的BST
    public boolean isValidBST() {
        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, int min, int max) {
        if (node == null) return true;

        if (node.val <= min || node.val >= max) {
            return false;
        }

        return isValidBST(node.left, min, node.val) &&
                isValidBST(node.right, node.val, max);
    }

    // 更新节点的值
    public boolean update(int oldValue, int newValue) {
        TreeNode node = search(root, oldValue);
        if (node != null) {
            node.val = newValue;
            return true;
        }
        return false;
    }

    // 打印树的结构
    public void printTree() {
        printTree(root, "Root: ", "");
    }

    private void printTree(TreeNode node, String details, String padding) {
        if (node != null) {
            System.out.println(padding + details + node.val);
            printTree(node.left, "Left: ", padding + "   ");
            printTree(node.right, "Right: ", padding + "   ");
        }
    }

    // 主方法（用于测试）
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // 插入节点
        int[] values = {10, 5, 15, 3, 7, 12, 18};
        for (int value : values) {
            bst.insert(value);
        }

        // 打印树结构
        System.out.println("BST Structure:");
        bst.printTree();

        // 前序遍历
        System.out.print("Pre-order Traversal: ");
        bst.preOrderTraversal();

        // 查找节点
        System.out.println("Contains 7: " + bst.contains(7));
        System.out.println("Contains 6: " + bst.contains(6));

        // 查找最小值和最大值
        System.out.println("Minimum Value: " + bst.findMinValue());
        System.out.println("Maximum Value: " + bst.findMaxValue());

        // 更新节点
        System.out.println("Update 15 to 16: " + bst.update(15, 16));

        // 删除节点
        System.out.println("Delete 5: " + bst.contains(5));
        bst.delete(5);
        System.out.println("After deletion: " + bst.contains(5));

        // 检查是否为有效的BST
        System.out.println("Is Valid BST: " + bst.isValidBST());

    }
}